// https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/description/

// 算法思路总结：
// 1. 二分查找寻找缺失的考勤编号
// 2. 根据数组元素值与下标的对应关系判断搜索方向
// 3. 元素值等于下标时向右搜索，不等时向左搜索
// 4. 返回第一个元素值与下标不相等的位置
// 5. 时间复杂度：O(log n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int takeAttendance(vector<int>& records) 
    {
        int m = records.size();
        int l = -1, r = m;

        while (l + 1 != r)
        {
            int mid = (l + r) >> 1;
            if (records[mid] == mid)
            {
                l = mid;
            }
            else
            {
                r = mid;
            }
        }

        return r;
    }
};

int main()
{
    vector<int> records1 = {0, 1, 2, 3, 5};
    vector<int> records2 = {0, 1, 2, 3, 4, 5, 6, 8};

    Solution sol;

    cout << sol.takeAttendance(records1) << endl;
    cout << sol.takeAttendance(records2) << endl;

    return 0;
}